package com.leetcode.normal;

import java.util.HashMap;
import java.util.Map;

/**
 * 无重复字符串的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 *
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 示例 1:
 *
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 * */
public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int start = 0,end = 0;
        int max = 0;
        char[] chars = s.toCharArray();
        Map<Character,Boolean> map = new HashMap<Character, Boolean>();
        int count = 0;
        while(end < chars.length){
            count ++;
            char c = chars[end];
            Boolean flag = map.get(c);
            if(flag == null || !flag) {
                map.put(c,true);
                end++;
            }
            else {
                map.put(chars[start],false);
                start++;
            }
            if(max < (end - start))
                max = end - start;
        }
        System.out.println(count);
        return max;
    }

    public int lengthOfLongestSubstring1(String s) {
        char[] chars = s.toCharArray();
        int max = 0;
        if (chars.length == 0) {
            return 0;
        } else if (chars.length == 1) {
            return 1;
        }
        //重复的坐标
        int len = 0;
        // 外层for循环  用来计算总长
        int j ;
        //内层for循环  用来计算总长
        int k;
        int count = 0;
        for (j=0; j <chars.length ; j++) {
            for (k = len;  k<j ; k++) {
                count ++;
                if (chars[j] == chars[k]) {
                    len = k+1 ;
                    break;
                }
            }
            max = max < j - len + 1? j - len + 1: max;
        }
        System.out.println(count);
        return max;
    }

    public static void main(String[] args) {
        LongestSubstring ls = new LongestSubstring();
        ls.lengthOfLongestSubstring("abcabcbb");
    }
}
